package com.hy;

import java.util.Stack;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最长有效括号
 *
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号
 * 子串
 * 的长度。
 * <p>
 * User:Mr.Du
 * Date:2024/3/19
 * Time:11:22
 */
public class LongestValidParentheses {
    public int longestValidParentheses1(String s) {
        Stack<Integer> stk = new Stack<>();
        // dp[i] 的定义：记录以 s[i-1] 结尾的最长合法括号子串长度
        int[] dp = new int[s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 遇到左括号，记录索引
                stk.push(i);
                // 左括号不可能是合法括号子串的结尾
                dp[i + 1] = 0;
            } else {
                // 遇到右括号
                if (!stk.isEmpty()) {
                    // 配对的左括号对应索引
                    int leftIndex = stk.pop();
                    // 以这个右括号结尾的最长子串长度
                    int len = 1 + i - leftIndex + dp[leftIndex];
                    dp[i + 1] = len;
                } else {
                    // 没有配对的左括号
                    dp[i + 1] = 0;
                }
            }
        }
        // 计算最长子串的长度
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;

    }

    /**
     * 计算字符串中最长有效括号子串的长度。
     *
     * @param s 给定的字符串，只包含 '(' 和 ')' 字符。
     * @return 返回最长有效括号子串的长度。
     */
    public int longestValidParentheses(String s) {
        int maxans = 0; // 记录最长有效括号子串的长度
        Stack<Integer> stack = new Stack<Integer>(); // 存放左括号索引的栈
        stack.push(-1); // 先压入一个-1，用于处理边界情况，避免出栈为空时的错误计算
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i); // 遇到左括号，压入其索引
            } else {
                stack.pop(); // 遇到右括号，弹出栈顶的左括号索引
                if (stack.isEmpty()) {
                    stack.push(i); // 如果栈为空，说明当前右括号没有匹配的左括号，将其索引压入栈
                } else {
                    maxans = Math.max(maxans, i - stack.peek()); // 计算当前有效括号长度，并更新最大值
                }
            }
        }
        return maxans;
    }



    public static void main(String[] args) {
        String s = "(()()()()";
        System.out.println(new LongestValidParentheses().longestValidParentheses(s));
    }

}


